-- 2022-8-9

---[[ 矩阵及多维数组

    -- 在Lua语言中 有两种方式来表示矩阵
    -- 第一种方式是使用一个不规则数组 即数组的数组 也就是一个所有元素均是另一个表的表

    -- 例如 可以使用如下的代码来创建一个全0元素的NxM维矩阵
    do
       local mt = {} -- 创建矩阵
       for i = 1, N do
        local row = {} -- 创建新的一行
        mt[i] = row
        for j = 1, M do
            row[j] = 0
        end
       end
    end

    -- 由于表在Lua语言中是一种对象 因此在创建矩阵时必须显式的创建每一行
    -- 一方面 这比在C语言中直接声明一个多维数组更加具体
    -- 另一方面 这也给我们提供了更多的灵活性
    -- 例如 只需将前例中的内层循环改为for j=1 i do ... end 就可以创建一个三角形矩阵
    -- 使用这套代码 三角形矩阵较原来的矩阵可以节约一半的内存

    -- 在Lua中表示矩阵的第二种方式是将两个索引合并为一个
    -- 典型情况下 我们通过将第一个索引乘以一个合适的常量再加上第二个索引来实现这种效果
    -- 这种方式下 我们可以使用如下的代码来创建一个全0元素的NxM维矩阵
    do
        local mt = {} -- 创建矩阵
        for i = 1, N do
            local aux = (i-1)*N
            for j = 1, M do
                mt[aux+j] = 0
            end
        end
    end

    -- 应用程序中经常会用到稀疏矩阵 这种矩阵中的大多数元素是0或nil
    -- 例如我们可以使用邻接矩阵来表示图
    -- 当矩阵(m,n)处的元素的值为x时 表示图中的节点m和n是相连的 连接的权重为x 若上述的两个节点不想连 那么矩阵(m,n)处元素的值为nil
    -- 如果要表示一个具有1万个节点的图(其中每个节点有5个邻居) 那么需要一个能包含1亿个元素的矩阵(10000列x10000列的方阵)
    -- 达式其中大约只有5万个元素不为nil(每行有5列不为nil 对应每个节点有5个邻居)
    -- 许多有关数据结构的书籍都会深入的讨论如何实现稀疏矩阵而不浪费空间 但Lua中很少需要这些技巧
    -- 因为 我们使用表实现的数组本来就是稀疏的
    -- 在第一种实现中(表的表) 需要1万个表 每个表包含5个元素 总共5万个元素
    -- 在第二种实现中 只需要一个表 其中需要包含5万个元素
    -- 无论哪种实现 都只有非nil的元素才占用空间

    -- 由于在有效元素之间存在空值 因此不能对稀疏矩阵使用长度运算符
    -- 这没什么大不了的 即使我们能够使用长度运算符 最好也不要那么做
    -- 对于大多数针对稀疏矩阵的操作来说 遍历空元素是非常低效的 相反 可以使用paris来只遍历非nil的元素
    -- 例如 考虑如何进行由不规则数组表示的稀疏矩阵的矩阵乘法
    -- 假设矩阵a[M,K]乘以矩阵b[K,N]的结果为矩阵c[M,N] 常见的矩阵相乘算法形如:
    do
        for i = 1, M do
            for j =1, N do
                c[i][j] = 0
                for k = 1, K do
                    c[i][j] = c[i][j] + a[i][k] * b[k][j]
                end
            end
        end
    end
    -- 外层的两个循环遍历了整个结果矩阵 然后使用内层循环计算每一个元素的值

    -- 对于使用不规则矩阵实现的稀疏矩阵 内层循环会有问题
    -- 由于内层循环遍历的是一列b而不是一行 因此不能在此处使用pairs:这个循环必须遍历每一行来检查对应的行是否在对应列中有元素
    -- 除了遍历了少量非0元素以外 这个循环还遍历了所有的0元素
    -- (由于不知道元素的位置 所以在其他场景下遍历一列也可能会有问题)

    -- 以下的算法与之前的示例非常类似 但是该算法调换了两个内层循环的顺序 通过这个简单的调整 该算法避免了遍历列
    --      假设'c'的元素都是0
    do
        for i = 1, M do
            for k = 1, K do
                for j = 1, N do
                    c[i][j] = c[i][j] + a[i][k] * b[k][j]
                end
            end
        end
    end
    -- 这样 中间的一层循环遍历行a[i] 而内层循环遍历行b[k] 这两个遍历都可以使用pairs来实现仅遍历非0元素
    -- 由于一个空的稀疏矩阵本身就是使用0填充的 所以对结果矩阵c的初始化没有任何问题

    -- 如下实例展示了上述算法的完整实现 其中使用了paris来处理稀疏的元素
    -- 这种实现只访问非nil元素 同时结果也是稀疏矩阵 此外 下面的代码还删去了结果中偶然为0的元素
    do
        function mult (a,b)
            local c = {} -- 结果矩阵
            for i = 1, #a do
                local resultLine = {}
                for k, va in pairs(a[i]) do
                    for j, vb in pairs(b[k]) do
                        local res = (resultLine[j] or 0) + va * vb
                        resultLine[j] = (res ~= 0) and res or nil
                    end
                end
                c[i] = resultLine
            end
            return c
        end
    end
--]]